package problem1049;

//1049.最后一块石头的重量
//https://leetcode.cn/problems/last-stone-weight-ii/description/

// class Solution {
//     public int lastStoneWeightII(int[] stones) {
//         int sum = 0;
//         for(int x:stones) {
//             sum += x;
//         }
//         int n = stones.length, m = sum/2;
//         int[][] dp = new int[n+1][m+1];
//         for(int i = 1; i<=n; i++) {
//             for(int j = 1; j<=m; j++) {
//                 dp[i][j] = dp[i-1][j];
//                 if(j-stones[i-1] >= 0) {
//                     dp[i][j] = Math.max(dp[i][j], dp[i-1][j-stones[i-1]] + stones[i-1]);
//                 }
//             }
//         }
//         return sum-2*dp[n][m];
//     }
// }

/*
dp[i][j]: 从前i个数中选,总和不超过j, 此时的最大和
a-b = sum

*/

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int x:stones) {
            sum += x;
        }
        int n = stones.length, m = sum/2;
        int[] dp = new int[m+1];
        for(int i = 1; i<=n; i++) {
            for(int j = m; j>=stones[i-1]; j--) {
                dp[j] = Math.max(dp[j], dp[j-stones[i-1]] + stones[i-1]);
            }
        }
        return sum-2*dp[m];
    }
}